home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / THINKC / 4_0 / FLEX-TC_ / ECS.C < prev    next >
Text File  |  1990-01-02  |  6KB  |  229 lines
  1. /* ecs - equivalence class routines */
  2.  
  3. /*
  4.  * Copyright (c) 1989 The Regents of the University of California.
  5.  * All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Vern Paxson.
  9.  * 
  10.  * The United States Government has rights in this work pursuant to
  11.  * contract no. DE-AC03-76SF00098 between the United States Department of
  12.  * Energy and the University of California.
  13.  *
  14.  * Redistribution and use in source and binary forms are permitted
  15.  * provided that the above copyright notice and this paragraph are
  16.  * duplicated in all such forms and that any documentation,
  17.  * advertising materials, and other materials related to such
  18.  * distribution and use acknowledge that the software was developed
  19.  * by the University of California, Berkeley.  The name of the
  20.  * University may not be used to endorse or promote products derived
  21.  * from this software without specific prior written permission.
  22.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  23.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  24.  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  25.  */
  26.  
  27. #ifndef lint
  28.  
  29. static char copyright[] =
  30.     "@(#) Copyright (c) 1989 The Regents of the University of California.\n";
  31. static char CR_continuation[] = "@(#) All rights reserved.\n";
  32.  
  33. static char rcsid[] =
  34.     "@(#) $Header: ecs.c,v 2.0 89/06/20 15:49:39 vern Locked $ (LBL)";
  35.  
  36. #endif
  37.  
  38. #include "flexdef.h"
  39.  
  40. /* ccl2ecl - convert character classes to set of equivalence classes
  41.  *
  42.  * synopsis
  43.  *    ccl2ecl();
  44.  */
  45.  
  46. ccl2ecl()
  47.  
  48.     {
  49.     int i, ich, newlen, cclp, ccls, cclmec;
  50.  
  51.     for ( i = 1; i <= lastccl; ++i )
  52.     {
  53.     /* we loop through each character class, and for each character
  54.      * in the class, add the character's equivalence class to the
  55.      * new "character" class we are creating.  Thus when we are all
  56.      * done, character classes will really consist of collections
  57.      * of equivalence classes
  58.      */
  59.  
  60.     newlen = 0;
  61.     cclp = cclmap[i];
  62.  
  63.     for ( ccls = 0; ccls < ccllen[i]; ++ccls )
  64.         {
  65.         ich = ccltbl[cclp + ccls];
  66.         cclmec = ecgroup[ich];
  67.         if ( cclmec > 0 )
  68.         {
  69.         ccltbl[cclp + newlen] = cclmec;
  70.         ++newlen;
  71.         }
  72.         }
  73.  
  74.     ccllen[i] = newlen;
  75.     }
  76.     }
  77.  
  78.  
  79. /* cre8ecs - associate equivalence class numbers with class members
  80.  *
  81.  * synopsis
  82.  *    int cre8ecs();
  83.  *    number of classes = cre8ecs( fwd, bck, num );
  84.  *
  85.  *  fwd is the forward linked-list of equivalence class members.  bck
  86.  *  is the backward linked-list, and num is the number of class members.
  87.  *  Returned is the number of classes.
  88.  */
  89.  
  90. int cre8ecs( fwd, bck, num )
  91. int fwd[], bck[], num;
  92.  
  93.     {
  94.     int i, j, numcl;
  95.  
  96.     numcl = 0;
  97.  
  98.     /* create equivalence class numbers.  From now on, abs( bck(x) )
  99.      * is the equivalence class number for object x.  If bck(x)
  100.      * is positive, then x is the representative of its equivalence
  101.      * class.
  102.      */
  103.  
  104.     for ( i = 1; i <= num; ++i )
  105.     if ( bck[i] == NIL )
  106.         {
  107.         bck[i] = ++numcl;
  108.         for ( j = fwd[i]; j != NIL; j = fwd[j] )
  109.         bck[j] = -numcl;
  110.         }
  111.  
  112.     return ( numcl );
  113.     }
  114.  
  115.  
  116. /* mkeccl - update equivalence classes based on character class xtions
  117.  *
  118.  * synopsis
  119.  *    char ccls[];
  120.  *    int lenccl, fwd[llsiz], bck[llsiz], llsiz;
  121.  *    mkeccl( ccls, lenccl, fwd, bck, llsiz );
  122.  *
  123.  * where ccls contains the elements of the character class, lenccl is the
  124.  * number of elements in the ccl, fwd is the forward link-list of equivalent
  125.  * characters, bck is the backward link-list, and llsiz size of the link-list
  126.  */
  127.  
  128. mkeccl( ccls, lenccl, fwd, bck, llsiz )
  129. char ccls[];
  130. int lenccl, fwd[], bck[], llsiz;
  131.  
  132.     {
  133.     int cclp, oldec, newec;
  134.     int cclm, i, j;
  135.  
  136. #define PROCFLG 0x80
  137.  
  138.     /* note that it doesn't matter whether or not the character class is
  139.      * negated.  The same results will be obtained in either case.
  140.      */
  141.  
  142.     cclp = 0;
  143.  
  144.     while ( cclp < lenccl )
  145.     {
  146.     cclm = ccls[cclp];
  147.     oldec = bck[cclm];
  148.     newec = cclm;
  149.  
  150.     j = cclp + 1;
  151.  
  152.     for ( i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i] )
  153.         { /* look for the symbol in the character class */
  154.         for ( ; j < lenccl && (ccls[j] <= i || (ccls[j] & PROCFLG)); ++j )
  155.         if ( ccls[j] == i )
  156.             {
  157.             /* we found an old companion of cclm in the ccl.
  158.              * link it into the new equivalence class and flag it as
  159.              * having been processed
  160.              */
  161.  
  162.             bck[i] = newec;
  163.             fwd[newec] = i;
  164.             newec = i;
  165.             ccls[j] |= PROCFLG;    /* set flag so we don't reprocess */
  166.  
  167.             /* get next equivalence class member */
  168.             /* continue 2 */
  169.             goto next_pt;
  170.             }
  171.  
  172.         /* symbol isn't in character class.  Put it in the old equivalence
  173.          * class
  174.          */
  175.  
  176.         bck[i] = oldec;
  177.  
  178.         if ( oldec != NIL )
  179.         fwd[oldec] = i;
  180.  
  181.         oldec = i;
  182. next_pt:
  183.         ;
  184.         }
  185.  
  186.     if ( bck[cclm] != NIL || oldec != bck[cclm] )
  187.         {
  188.         bck[cclm] = NIL;
  189.         fwd[oldec] = NIL;
  190.         }
  191.  
  192.     fwd[newec] = NIL;
  193.  
  194.     /* find next ccl member to process */
  195.  
  196.     for ( ++cclp; (ccls[cclp] & PROCFLG) && cclp < lenccl; ++cclp )
  197.         {
  198.         /* reset "doesn't need processing" flag */
  199.         ccls[cclp] &= ~PROCFLG;
  200.         }
  201.     }
  202.     }
  203.  
  204.  
  205. /* mkechar - create equivalence class for single character
  206.  *
  207.  * synopsis
  208.  *    int tch, fwd[], bck[];
  209.  *    mkechar( tch, fwd, bck );
  210.  */
  211.  
  212. mkechar( tch, fwd, bck )
  213. int tch, fwd[], bck[];
  214.  
  215.     {
  216.     /* if until now the character has been a proper subset of
  217.      * an equivalence class, break it away to create a new ec
  218.      */
  219.  
  220.     if ( fwd[tch] != NIL )
  221.     bck[fwd[tch]] = bck[tch];
  222.  
  223.     if ( bck[tch] != NIL )
  224.     fwd[bck[tch]] = fwd[tch];
  225.  
  226.     fwd[tch] = NIL;
  227.     bck[tch] = NIL;
  228.     }
  229.